這次我們來改寫這個。

在Java中，我們這樣寫。

import java.util.ArrayList;
import java.util.List;

public class MinimumPathSum {
    public static void main(String[] args) {
        //int[][] grid = {{1, 3, 1}, {1, 5, 1},{4, 2, 1}};
        int[][] grid = {{1, 2, 3}, {4, 5, 6}};
        List<Integer> path = minPath(grid);
        int sum = 0;
        for (int i = 0; i<path.size()-1;i++) {
            System.out.print(path.get(i) +", ");
            sum += path.get(i);
        }
        sum += path.get(path.size()-1);
        System.out.print(path.get(path.size()-1)+" = "+sum);
    }
    public static List<Integer> minPath(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];

        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }
        for (int j = 1; j < m; j++) {
            dp[j][0] = dp[j-1][0] + grid[j][0];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
            }
        }
        List<Integer> path = new ArrayList<>();
        int i = m-1, j = n-1;
        while (i > 0 || j > 0) {
            path.add(0, grid[i][j]);
            if (i == 0) {
                j--;
            } else if (j == 0) {
                i--;
            } else if (dp[i-1][j] < dp[i][j-1]) {
                i--;
            } else {
                j--;
            }
        }
        path.add(0, grid[0][0]);
        return path;
    }
}

各位可以看到，土法煉鋼，非常的麻煩。

然而Kotlin我們這樣寫。

fun main() {
    //val grid = arrayOf(intArrayOf(1, 3, 1), intArrayOf(1, 5, 1), intArrayOf(4, 2, 1))
    val grid = arrayOf(intArrayOf(1, 2, 3), intArrayOf(4, 5, 6))
    val path = minPath(grid)
    var sum = 0
    for (i in 0 until path.size - 1) {
        print("${path[i]}, ")
        sum += path[i]
    }
    sum += path[path.size - 1]
    print("${path[path.size - 1]} = $sum")
}

fun minPath(grid: Array<IntArray>): List<Int> {
    val m = grid.size
    val n = grid[0].size
    val dp = Array(m) { IntArray(n) }
    dp[0][0] = grid[0][0]

    for (i in 1 until n) {
        dp[0][i] = dp[0][i - 1] + grid[0][i]
    }
    for (j in 1 until m) {
        dp[j][0] = dp[j - 1][0] + grid[j][0]
    }
    for (i in 1 until m) {
        for (j in 1 until n) {
            dp[i][j] = minOf(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        }
    }
    val path = mutableListOf<Int>()
    var i = m - 1
    var j = n - 1
    while (i > 0 || j > 0) {
        path.add(0, grid[i][j])
        when {
            i == 0 -> j--
            j == 0 -> i--
            dp[i - 1][j] < dp[i][j - 1] -> i--
            else -> j--
        }
    }
    path.add(0, grid[0][0])
    return path
}

明顯的方便了許多，對吧，各位，今天就到這裡結束，88。

下回，鐵人賽之死，記得要收看喔。